package 二叉树;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 多叉树层序遍历 {
    public static void main(String[] args) {
    }
}


// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};


class  Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Node> que = new LinkedList<>();

        if(root==null){
            return list;
        }

        que.offer(root);

        while(!que.isEmpty()){
            int size = que.size();
            List<Integer> subList = new ArrayList<>();
            for(int i = 0; i < size; i++){
                Node node = que.poll();
                subList.add(node.val);
                List<Node> children = node.children;
                if (children == null || children.size() == 0) {
                    continue;
                }

                for(Node child: children){
                    if(child!=null){
                        que.offer(child);
                    }
                }

            }
            list.add(subList);
        }
        return list;
    }
}